package DynamicProgramming;

/**
 * @author: Darven
 * @createTime: 2025-08-01  12:35
 * @description: TODO
 */
public class P673 {
    public static void main(String[] args) {
        P673Demo p673Demo = new P673Demo();
        System.out.println(p673Demo.findNumberOfLIS(new int[]{1,2,4,3,5,4,7,2}));
    }
}

class P673Demo{
    public int findNumberOfLIS(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int[] dp=new int[nums.length];
        int[] count=new int[nums.length];
        int maxNums=0;
        for(int i=0;i<nums.length;i++){
            dp[i]=1;
            count[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(dp[i]<dp[j]+1){
                        dp[i]=dp[j]+1;
                        count[i]=count[j];
                    }
                    else if(dp[i]==dp[j]+1){
                        count[i]+=count[j];
                    }
                }
            }
            maxNums=Math.max(maxNums, dp[i]);
        }
        int num=0;
        for(int i=0;i<nums.length;i++){
            if((maxNums)==dp[i]){
                num+=count[i];
            }
        }
        return num;
    }
}
